class Solution {
    static int[] par;
    static int[] size;
    public int findPar(int u) {
        return u == par[u] ? u : (par[u] = findPar(par[u]));
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        par = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            par[i] = i;
            size[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1 && i != j) {
                    int p1 = findPar(i);
                    int p2 = findPar(j);
                    if (p1 != p2) {
                        if (size[p1] > size[p2]) {
                            par[p2] = p1;
                            size[p1] += size[p1];
                        } else {
                            par[p1] = p2;
                            size[p2] += size[p1];
                        }
                    }
                }
            }
        }
        int ans = initial[0];
        boolean[] moreThanOneInfected = new boolean[n];
        for (int i = 0; i < initial.length; i++) {
            int p1 = findPar(initial[i]);
            for (int j = i + 1; j < initial.length; j++) {
                int p2 = findPar(initial[j]);
                if (p1 == p2) {
                    moreThanOneInfected[initial[i]] = true;
                    moreThanOneInfected[initial[j]] = true;
                }
            }
        }
        for (int i = 1; i < initial.length; i++) {
            int p1 = par[ans];
            int p2 = par[initial[i]];
            if (p1 != p2 && !moreThanOneInfected[initial[i]]) {
                if (moreThanOneInfected[ans] || size[p2] > size[p1]) {
                     ans = initial[i];
                } else if (size[p1] == size[p2]) {
                     ans = Math.min(ans, initial[i]);
                }
            } else {
                ans = Math.min(ans, initial[i]);
            } 
        }
        return ans;
    }
}